package slidingwindow;

/**
 * @author kaho
 * @since 2021/2/19
 */
public class _1004_最大连续1的个数_III {

    /**
     *
     * 给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
     *
     * 返回仅包含 1 的最长（连续）子数组的长度。
     */
    public static int longestOnes(int[] nums, int k) {
        int left = 0, right =0,zero= 0;
        int max =0;
        while (right<nums.length){
            if (nums[right]==0){
                zero++;
            }
            while (zero>k){
                if (nums[left++]==0){
                    zero --;
                }
            }
            max = Math.max(max, right-left+1);

            right++;
        }
        return max;
    }

    public static int longestOnes1(int[] nums, int k) {
        int n = nums.length;
        // f(i,j) 代表考虑前 i 个数（并以 i 为结尾的），最大翻转次数为 j 时，连续 1 的最大长度
        int[][] f = new int[2][k + 1];
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                if (nums[i - 1] == 1) {
                    f[i & 1][j] = f[(i - 1) & 1][j] + 1;
                } else {
                    if (j == 0) {
                        f[i & 1][j] = 0;
                    } else {
                        f[i & 1][j] = j - 1 >= 0 ? f[(i - 1) & 1][j - 1] + 1 : 1;
                    }
                }
                ans = Math.max(ans, f[i & 1][j]);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int i = longestOnes(new int[]{0, 1, 1, 1, 0, 0, 0, 1, 0, 0}, 2);
    }
}
